{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sum Game"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #math #game-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数学 #博弈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sumGame"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #求和游戏"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>Alice 和 Bob 玩一个游戏，两人轮流行动，<strong>Alice 先手</strong> 。</p>\n",
    "\n",
    "<p>给你一个 <strong>偶数长度</strong> 的字符串 <code>num</code> ，每一个字符为数字字符或者 <code>'?'</code> 。每一次操作中，如果 <code>num</code> 中至少有一个 <code>'?'</code> ，那么玩家可以执行以下操作：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>选择一个下标 <code>i</code> 满足 <code>num[i] == '?'</code> 。</li>\n",
    "\t<li>将 <code>num[i]</code> 用 <code>'0'</code> 到 <code>'9'</code> 之间的一个数字字符替代。</li>\n",
    "</ol>\n",
    "\n",
    "<p>当 <code>num</code> 中没有<span style=\"\"> </span><code>'?'</code> 时，游戏结束。</p>\n",
    "\n",
    "<p>Bob 获胜的条件是 <code>num</code> 中前一半数字的和 <strong>等于</strong> 后一半数字的和。Alice 获胜的条件是前一半的和与后一半的和 <strong>不相等</strong> 。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，游戏结束时 <code>num = \"243801\"</code> ，那么 Bob 获胜，因为 <code>2+4+3 = 8+0+1</code> 。如果游戏结束时 <code>num = \"243803\"</code> ，那么 Alice 获胜，因为 <code>2+4+3 != 8+0+3</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>在 Alice 和 Bob 都采取 <strong>最优</strong> 策略的前提下，如果 Alice 获胜，请返回 <code>true</code> ，如果 Bob 获胜，请返回 <code>false</code> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>num = \"5023\"\n",
    "<b>输出：</b>false\n",
    "<b>解释：</b>num 中没有 '?' ，没法进行任何操作。\n",
    "前一半的和等于后一半的和：5 + 0 = 2 + 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>num = \"25??\"\n",
    "<b>输出：</b>true\n",
    "<strong>解释：</strong>Alice 可以将两个 '?' 中的一个替换为 '9' ，Bob 无论如何都无法使前一半的和等于后一半的和。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>num = \"?3295???\"\n",
    "<b>输出：</b>false\n",
    "<b>解释：</b>Bob 总是能赢。一种可能的结果是：\n",
    "- Alice 将第一个 '?' 用 '9' 替换。num = \"93295???\" 。\n",
    "- Bob 将后面一半中的一个 '?' 替换为 '9' 。num = \"932959??\" 。\n",
    "- Alice 将后面一半中的一个 '?' 替换为 '2' 。num = \"9329592?\" 。\n",
    "- Bob 将后面一半中最后一个 '?' 替换为 '7' 。num = \"93295927\" 。\n",
    "Bob 获胜，因为 9 + 3 + 2 + 9 = 5 + 9 + 2 + 7 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 <= num.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>num.length</code> 是 <strong>偶数</strong> 。</li>\n",
    "\t<li><code>num</code> 只包含数字字符和 <code>'?'</code> 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sum-game](https://leetcode.cn/problems/sum-game/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sum-game](https://leetcode.cn/problems/sum-game/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"5023\"', '\"25??\"', '\"?3295???\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        \n",
    "        def get(s: str) -> (int, int):\n",
    "            nn = qq = 0\n",
    "            for ch in s:\n",
    "                if ch == \"?\":\n",
    "                    qq += 1\n",
    "                else:\n",
    "                    nn += int(ch)\n",
    "            return nn, qq\n",
    "        \n",
    "        n0, q0 = get(num[:n//2])\n",
    "        n1, q1 = get(num[n//2:])\n",
    "        \n",
    "        return (q0 + q1) % 2 == 1 or n0 - n1 != (q1 - q0) * 9 // 2\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        \n",
    "        def get(s: str) -> (int, int):\n",
    "            nn = qq = 0\n",
    "            for ch in s:\n",
    "                if ch == \"?\":\n",
    "                    qq += 1\n",
    "                else:\n",
    "                    nn += int(ch)\n",
    "            return nn, qq\n",
    "        \n",
    "        n0, q0 = get(num[:n//2])\n",
    "        n1, q1 = get(num[n//2:])\n",
    "        \n",
    "        return (q0 + q1) % 2 == 1 or n0 - n1 != (q1 - q0) * 9 // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        n = len(num) // 2\n",
    "        cnt1 = cnt2 = 0\n",
    "        s1 = s2 = 0\n",
    "        for ch in num[:n]:\n",
    "            if ch == '?':\n",
    "                cnt1 += 1\n",
    "            else:\n",
    "                s1 += ord(ch) - ord('0')\n",
    "        \n",
    "        for ch in num[n:]:\n",
    "            if ch == '?':\n",
    "                cnt2 += 1\n",
    "            else:\n",
    "                s2 += ord(ch) - ord('0')\n",
    "        \n",
    "        if (cnt1 + cnt2) & 1:\n",
    "            return True\n",
    "        \n",
    "        if cnt1 >= cnt2 and s1 <= s2:\n",
    "            return s2 - s1 != (cnt1 - cnt2) * 9 // 2\n",
    "        elif cnt1 < cnt2 and s1 > s2:\n",
    "            return s1 - s2 != (cnt2 - cnt1) * 9 // 2\n",
    "        \n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        sum1 = 0\n",
    "        sum2 = 0\n",
    "        cnt1 = 0\n",
    "        cnt2 = 0\n",
    "        for i in range(n // 2):\n",
    "            if num[i] == '?':\n",
    "                cnt1 += 1\n",
    "                sum1 += 4.5\n",
    "            else:\n",
    "                sum1 += int(num[i])\n",
    "        for i in range(n // 2, n):\n",
    "            if num[i] == '?':\n",
    "                cnt2 += 1\n",
    "                sum2 += 4.5\n",
    "            else:\n",
    "                sum2 += int(num[i])\n",
    "        if (cnt1 + cnt2) % 2:\n",
    "            return True\n",
    "        if sum1 == sum2:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        \n",
    "        def get(s: str) -> (int, int):\n",
    "            nn = qq = 0\n",
    "            for ch in s:\n",
    "                if ch == \"?\":\n",
    "                    qq += 1\n",
    "                else:\n",
    "                    nn += int(ch)\n",
    "            return nn, qq\n",
    "        \n",
    "        n0, q0 = get(num[:n//2])\n",
    "        n1, q1 = get(num[n//2:])\n",
    "        \n",
    "        return (q0 + q1) % 2 == 1 or n0 - n1 != (q1 - q0) * 4.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        n=len(num)//2\n",
    "        s1,s2=0,0\n",
    "        w1,w2=0,0\n",
    "        for i in range(n):\n",
    "            if num[i]==\"?\":\n",
    "                w1+=1\n",
    "            else:\n",
    "                s1+=int(num[i])\n",
    "        for j in range(n,2*n):\n",
    "            if num[j]==\"?\":\n",
    "                w2+=1\n",
    "            else:\n",
    "                s2+=int(num[j])\n",
    "        return (w1+w2)%2!=0 or (s1-s2)+((9*(w1-w2))//2)!=0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        sum1 = 0\n",
    "        sum2 = 0 \n",
    "        cn1 = 0\n",
    "        cn2 = 0\n",
    "        half = len(num) // 2\n",
    "        for i in range(0, half):\n",
    "            if num[i] == \"?\":\n",
    "                cn1 += 1\n",
    "            else:\n",
    "                sum1 += int(num[i])\n",
    "        for i in range(half, len(num)):\n",
    "            if num[i] == \"?\":\n",
    "                cn2 += 1\n",
    "            else:\n",
    "                sum2 +=int(num[i])\n",
    "        \n",
    "        if (cn1 + cn2) % 2:\n",
    "            return True\n",
    "\n",
    "        ans = 4.5*(cn1-cn2) + sum1-sum2\n",
    "        return round(ans) != 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        \n",
    "        def get(s: str) -> (int, int):\n",
    "            nn = qq = 0\n",
    "            for ch in s:\n",
    "                if ch == \"?\":\n",
    "                    qq += 1\n",
    "                else:\n",
    "                    nn += int(ch)\n",
    "            return nn, qq\n",
    "        \n",
    "        n0, q0 = get(num[:n//2])\n",
    "        n1, q1 = get(num[n//2:])\n",
    "        \n",
    "        return (q0 + q1) % 2 == 1 or n0 - n1 != (q1 - q0) * 9 // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        l = len(num)\n",
    "        cl = 0\n",
    "        cr = 0\n",
    "        sl = 0\n",
    "        sr = 0\n",
    "        for i in range(l//2):\n",
    "            if num[i] == '?':\n",
    "                cl += 1\n",
    "            else:\n",
    "                sl += int(num[i])\n",
    "            if num[l-1-i] == '?':\n",
    "                cr += 1\n",
    "            else:\n",
    "                sr += int(num[l-1-i])\n",
    "        return (cl-cr) * 9 != -2 * (sl-sr)\n",
    "\n",
    "        # ????"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        n0, n1, q0, q1 = 0, 0, 0, 0\n",
    "        for i in range(n // 2):\n",
    "            if num[i] == '?':\n",
    "                q0 += 1\n",
    "            else:\n",
    "                n0 += int(num[i])\n",
    "            if num[i + n // 2] == '?':\n",
    "                q1 += 1\n",
    "            else:\n",
    "                n1 += int(num[i + n // 2])\n",
    "        if (q0 + q1) % 2 != 0:\n",
    "            return True\n",
    "        return not(n0 - n1 == (q1 - q0) // 2 * 9)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        l1, r1, l2, r2 = 0, 0, 0, 0\n",
    "        a = 1\n",
    "        for i in range(n):\n",
    "            if num[i] == '?':\n",
    "                if i < n // 2:\n",
    "                    if a: l1 += 9\n",
    "                    else: l2 += 9\n",
    "                else:\n",
    "                    if a: r2 += 9\n",
    "                    else: r1 += 9\n",
    "                a ^= 1\n",
    "            else:\n",
    "                if i < n // 2:\n",
    "                    l1 += int(num[i])\n",
    "                    l2 += int(num[i])\n",
    "                else:\n",
    "                    r1 += int(num[i])\n",
    "                    r2 += int(num[i])\n",
    "        return not (l1 <= r1 and l2 >= r2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        sum1 = 0\n",
    "        sum2 = 0\n",
    "        cnt1 = 0\n",
    "        cnt2 = 0\n",
    "        for i in range(n // 2):\n",
    "            if num[i] == '?':\n",
    "                cnt1 += 1\n",
    "                sum1 += 4.5\n",
    "            else:\n",
    "                sum1 += int(num[i])\n",
    "        for i in range(n // 2, n):\n",
    "            if num[i] == '?':\n",
    "                cnt2 += 1\n",
    "                sum2 += 4.5\n",
    "            else:\n",
    "                sum2 += int(num[i])\n",
    "        if (cnt1 + cnt2) % 2:\n",
    "            return True\n",
    "        if sum1 == sum2:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        \n",
    "        def get(s: str) -> (int, int):\n",
    "            nn = qq = 0\n",
    "            for ch in s:\n",
    "                if ch == \"?\":\n",
    "                    qq += 1\n",
    "                else:\n",
    "                    nn += int(ch)\n",
    "            return nn, qq\n",
    "        \n",
    "        n0, q0 = get(num[:n//2])\n",
    "        n1, q1 = get(num[n//2:])\n",
    "        \n",
    "        return (q0 + q1) % 2 == 1 or n0 - n1 != (q1 - q0) * 9 // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        nd, qd = 0, 0\n",
    "        for i, j in zip(num[:len(num)//2], num[len(num)//2:]):\n",
    "            if i=='?': qd += 1\n",
    "            else: nd += int(i)\n",
    "            if j=='?': qd -= 1\n",
    "            else: nd -= int(j)\n",
    "        return -nd != qd/2*9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        n=len(num)\n",
    "        def get(s):\n",
    "            nn=qq=0\n",
    "            for ch in s:\n",
    "                if ch=='?':\n",
    "                    qq+=1\n",
    "                else:\n",
    "                    nn+=int(ch)\n",
    "            return nn,qq\n",
    "        n0,q0=get(num[:n//2])\n",
    "        n1,q1=get(num[n//2:])\n",
    "\n",
    "        return (q0+q1)%2 ==1 or n0-n1 !=(q1-q0)*9//2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        def get_sum_and_q_cnt(start, end):\n",
    "            current_sum = 0\n",
    "            cnt = 0\n",
    "            for ii in range(start, end):\n",
    "                if num[ii] == '?':\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    current_sum += int(num[ii])\n",
    "            \n",
    "            return current_sum, cnt\n",
    "        \n",
    "        s0, q0 = get_sum_and_q_cnt(0, len(num) // 2)\n",
    "        s1, q1 = get_sum_and_q_cnt(len(num) // 2, len(num))\n",
    "\n",
    "        return (q0 + q1) % 2 == 1 or (s0 - s1 != (q1 - q0) * 9 // 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        sum1 = 0\n",
    "        sum2 = 0\n",
    "        cnt1 = 0\n",
    "        cnt2 = 0\n",
    "        for i in range(n // 2):\n",
    "            if num[i] == '?':\n",
    "                cnt1 += 1\n",
    "                # sum1 += 4.5\n",
    "            else:\n",
    "                sum1 += int(num[i])\n",
    "        for i in range(n // 2, n):\n",
    "            if num[i] == '?':\n",
    "                cnt2 += 1\n",
    "                # sum2 += 4.5\n",
    "            else:\n",
    "                sum2 += int(num[i])\n",
    "        if (cnt1 + cnt2) % 2:\n",
    "            return True\n",
    "        # if sum1 == sum2:\n",
    "        #     return False\n",
    "        # return True\n",
    "        return 9 * (cnt1 - cnt2) / 2 + sum1 - sum2 != 0;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def sumGame(self, num: str) -> bool:\r\n",
    "        # 如果 ALice 先手 并且有奇数个问号，那么一定能赢 \r\n",
    "        # 如果问号个数为偶数 则选择前后差值最大化的变化 \r\n",
    "\r\n",
    "        n = len(num) \r\n",
    "        def get(s):\r\n",
    "            ss = cnt = 0\r\n",
    "            for ch in s:\r\n",
    "                if ch == '?':\r\n",
    "                    cnt += 1\r\n",
    "                else:\r\n",
    "                    ss += int(ch) \r\n",
    "            return ss, cnt \r\n",
    "        pres, precnt = get(num[:n//2])\r\n",
    "        posts, postcnt = get(num[n//2:])\r\n",
    "        return (precnt + postcnt) % 2 == 1 or 2 * (pres - posts) != 9 * (postcnt - precnt)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        \"\"\"\n",
    "        :type num: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        n = len(num)\n",
    "        m = num.count('?')\n",
    "        if m % 2 == 1:\n",
    "            return True\n",
    "        p = num[:n//2].count('?')\n",
    "        q = num[n//2:].count('?')\n",
    "        sm1 = 0\n",
    "        sm2 = 0\n",
    "        for i in num[:n//2]:\n",
    "            if i != '?':\n",
    "                sm1 += int(i)\n",
    "        for i in num[n//2:]:\n",
    "            if i != '?':\n",
    "                sm2 += int(i)\n",
    "        n1 = p - q\n",
    "        n2 = sm1 - sm2\n",
    "        #数字 必须等于 问号个数 /2 * 9,且不能在同一边，不然都是true;\n",
    "        if (n1 // 2) * -9 == n2:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, a: str) -> bool:\n",
    "        n = len(a)\n",
    "        s1,s2,q1,q2 = 0,0,0,0\n",
    "        for i in range(n):\n",
    "            if a[i] == '?':\n",
    "                if i < n//2: q1 += 1\n",
    "                else: q2 += 1\n",
    "            else:\n",
    "                if i < n//2: s1 += ord(a[i])-ord('0')\n",
    "                else: s2 += ord(a[i])-ord('0')\n",
    "        if (q1+q2)%2: return True\n",
    "        return (s1-s2)+9*(q1-q2)//2 != 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        pre_sum = pre_cnt = 0\n",
    "        for i in range(n//2):\n",
    "            if num[i] == \"?\":\n",
    "                pre_cnt += 1\n",
    "            else:\n",
    "                pre_sum += int(num[i])\n",
    "        post_sum = post_cnt = 0\n",
    "        for i in range(n // 2, n):\n",
    "            if num[i] == \"?\":\n",
    "                post_cnt += 1\n",
    "            else:\n",
    "                post_sum += int(num[i])\n",
    "        x, y =pre_cnt, post_cnt\n",
    "        # 左边最大\n",
    "        pre = pre_sum\n",
    "        post = post_sum\n",
    "        for i in range(pre_cnt+post_cnt):\n",
    "            if i % 2 == 0:\n",
    "                if pre_cnt:\n",
    "                    pre += 9\n",
    "                    pre_cnt -= 1\n",
    "                else:\n",
    "                    post += 0\n",
    "                    post_cnt -= 1\n",
    "            else:\n",
    "                if pre_cnt:\n",
    "                    pre_cnt -= 1\n",
    "                    pre += 0\n",
    "                else:\n",
    "                    post += 9\n",
    "                    post_cnt -= 1\n",
    "        if pre > post:\n",
    "            return True\n",
    "        \n",
    "        # 右边最大\n",
    "        pre = pre_sum\n",
    "        post = post_sum\n",
    "        pre_cnt, post_cnt = x, y\n",
    "        for i in range(pre_cnt+post_cnt):\n",
    "            if i % 2 == 0:\n",
    "                if post_cnt:\n",
    "                    post += 9\n",
    "                    post_cnt -= 1\n",
    "                else:\n",
    "                    pre_cnt -= 1\n",
    "                    pre += 0\n",
    "            else:\n",
    "                if post_cnt:\n",
    "                    post_cnt -= 1\n",
    "                    post += 0\n",
    "                else:\n",
    "                    pre_cnt -= 1\n",
    "                    pre += 9\n",
    "        if post > pre:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        def get_sum_and_q_cnt(start, end):\n",
    "            current_sum = 0\n",
    "            cnt = 0\n",
    "            for ii in range(start, end):\n",
    "                if num[ii] == '?':\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    current_sum += int(num[ii])\n",
    "            \n",
    "            return current_sum, cnt\n",
    "        \n",
    "        s0, q0 = get_sum_and_q_cnt(0, len(num) // 2)\n",
    "        s1, q1 = get_sum_and_q_cnt(len(num) // 2, len(num))\n",
    "\n",
    "        # ？为奇数：Alice一定可以最后走，一定可以破坏平衡\n",
    "        # ？为偶数：Bob先通过模仿Alice变的数字，可以相当于左右抵消，最后只有一边有？，所以先q1-q0\n",
    "        # Bob（平衡者）想用这剩下的问号来达到平衡，即要用剩下的问号（两个一组，因为要对抗Alice）来补足两边的差值\n",
    "        # 唯一可能的情况是差值刚好是9的倍数；Bob每次第二个走的时候，都可以把当前这组问号的和补足到9，如果差值刚好是**问号组数个**9的倍数就可以赢；不然Alice总是可以第一个走的时候把问号数字变成9；比如差8，Alice就可以出9，和就已经超了，Bob就寄了\n",
    "        return (q0 + q1) % 2 == 1 or (s0 - s1 != (q1 - q0) * 9 // 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        left, right = 0, len(num) - 1\n",
    "        left_q_num, right_q_num, left_sum, right_sum = 0, 0, 0, 0\n",
    "        while left < right:\n",
    "            if num[left] == \"?\":\n",
    "                left_q_num += 1\n",
    "            else:\n",
    "                left_sum += ord(num[left]) - ord(\"0\")\n",
    "            left += 1\n",
    "            if num[right] == \"?\":\n",
    "                right_q_num += 1\n",
    "            else:\n",
    "                right_sum += ord(num[right]) - ord(\"0\")\n",
    "            right -= 1\n",
    "        if (left_q_num + right_q_num) % 2 != 0:\n",
    "            return True\n",
    "        if (left_sum - right_sum) * 2 == 9 * (right_q_num - left_q_num):\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        # 判断特殊情况\n",
    "        if \"?\" not in num:\n",
    "            s1 = 0\n",
    "            s2 = 0\n",
    "            for i in range(n):\n",
    "                if i < n / 2:\n",
    "                    s1 += int(num[i])\n",
    "                else:\n",
    "                    s2 += int(num[i])\n",
    "            return s1 != s2\n",
    "        # 判断?为奇数时\n",
    "        total_num = 0\n",
    "        for value in num:\n",
    "            if value == \"?\":\n",
    "                total_num += 1\n",
    "        if total_num % 2 == 1:\n",
    "            return True\n",
    "        # 接下来只剩?为偶数的情况\n",
    "        ## 如果两边和中存在比较大的数，那么如果大数那边问号比较多那么A必定会天上9时差距拉大，而B只能在\n",
    "        ## 较小数那边天上9以缩小差距\n",
    "        ## 所以最终决定权还是在？较多的一方\n",
    "        left_wenhao = 0\n",
    "        right_wenhao = 0\n",
    "        left_num = 0\n",
    "        right_num = 0\n",
    "        for i in range(n):\n",
    "            if i < n / 2:\n",
    "                if num[i] != \"?\":\n",
    "                    left_num += int(num[i])\n",
    "                else:\n",
    "                    left_wenhao += 1\n",
    "            else:\n",
    "                if num[i] != \"?\":\n",
    "                    right_num += int(num[i])\n",
    "                else:\n",
    "                    right_wenhao += 1\n",
    "        # 判断左右两边大小和问号数()\n",
    "        if left_num > right_num and left_wenhao >= right_wenhao:\n",
    "            return True\n",
    "        if left_num < right_num and left_wenhao <= right_wenhao:\n",
    "            return True \n",
    "        # 判断最后一种情况(只有较小数加上问号差的一半*9 == 较大数B才能赢)\n",
    "        m = (max(left_wenhao,right_wenhao) - min(left_wenhao,right_wenhao)) / 2\n",
    "        if min(left_num,right_num) + m * 9 == max(left_num,right_num):\n",
    "            return False\n",
    "        else:\n",
    "            return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        q_count=0\n",
    "        s=[0,0]\n",
    "        q=[0,0]\n",
    "        l = len(num)\n",
    "        for i in range(l):\n",
    "            if num[i]=='?':\n",
    "                q_count+=1\n",
    "                if i< l//2:\n",
    "                    q[0]+=1\n",
    "                else:\n",
    "                    q[1]+=1\n",
    "            else:\n",
    "                if i< l//2:\n",
    "                    s[0]+=int(num[i])\n",
    "                else:\n",
    "                    s[1]+=int(num[i])\n",
    "        b_t = q_count//2\n",
    "        small = 0\n",
    "        if s[0]>=s[1]:\n",
    "            small=1\n",
    "        big = 1-small\n",
    "        if s[small]+(q[small]-b_t)*9 > s[big]:\n",
    "            return True\n",
    "        if (b_t-q[big])*9 + s[small] >=s[big]:\n",
    "            if q_count%2==0:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        n=len(num)\n",
    "        nl=[]\n",
    "        left=0\n",
    "        right=0\n",
    "        leftq,rightq=0,0\n",
    "        for s in num[:n//2]:\n",
    "            if s!='?':\n",
    "                left+=int(s)\n",
    "            else:\n",
    "                leftq+=1\n",
    "        for s in num[n//2:n]:\n",
    "            if s!='?':\n",
    "                right+=int(s)\n",
    "            else:\n",
    "                rightq+=1\n",
    "        if (leftq+rightq)%2==1:\n",
    "            return True\n",
    "        else:\n",
    "            return (leftq-rightq)*4.5!=right-left\n",
    "          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        \n",
    "        def get(s: str) -> (int, int):\n",
    "            nn = qq = 0\n",
    "            for ch in s:\n",
    "                if ch == \"?\":\n",
    "                    qq += 1\n",
    "                else:\n",
    "                    nn += int(ch)\n",
    "            return nn, qq\n",
    "        \n",
    "        n0, q0 = get(num[:n//2])\n",
    "        n1, q1 = get(num[n//2:])\n",
    "        \n",
    "        return (q0 + q1) % 2 == 1 or n0 - n1 != (q1 - q0) * 9 // 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        n = len(num)\n",
    "        lsum = sum([int(x) for x in num[:n//2] if x != '?'])\n",
    "        rsum = sum([int(x) for x in num[n//2:] if x != '?'])\n",
    "\n",
    "        lqus = len([x for x in num[:n//2] if x == '?'])\n",
    "        rqus = len([x for x in num[n//2:] if x == '?'])\n",
    "\n",
    "        if lsum == rsum:\n",
    "            if lqus != rqus:\n",
    "                return True\n",
    "\n",
    "        if lsum < rsum:\n",
    "            if lqus < rqus:\n",
    "                return True\n",
    "            if (lqus - rqus) // 2 * 9 < rsum - lsum:\n",
    "                return True\n",
    "            if ((lqus - rqus) - (lqus - rqus) // 2) * 9 + lsum > rsum:\n",
    "                return True\n",
    "\n",
    "        if lsum > rsum:\n",
    "            if rqus < lqus:\n",
    "                return True\n",
    "            if (rqus - lqus) // 2 * 9 < lsum - rsum:\n",
    "                return True\n",
    "            if ((rqus - lqus) - (rqus - lqus) // 2) * 9 + rsum > lsum:\n",
    "                return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        n=len(num)\n",
    "        n1=n//2\n",
    "        b1=[]\n",
    "        b2=[]\n",
    "        for i in num[0:n1]:\n",
    "            if i != '?':\n",
    "                b1.append(int(i))\n",
    "        for i in num[n1:n]:\n",
    "            if i != '?':\n",
    "                b2.append(int(i))\n",
    "        n2=n1-len(b1)\n",
    "        n3=n1-len(b2)\n",
    "        c=sum(b1)-sum(b2)\n",
    "        if n2==n3:\n",
    "            return c!=0\n",
    "        if n2<n3:\n",
    "            return sum(b1)-sum(b2)!=4.5*(n3-n2)\n",
    "        if n2>n3:\n",
    "            return sum(b2)-sum(b1)!=4.5*(n2-n3)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        n=len(num)\n",
    "        n1=n//2\n",
    "        a1=num[0:n1]\n",
    "        a2=num[n1:n]\n",
    "        b1=[]\n",
    "        b2=[]\n",
    "        for i in a1:\n",
    "            if i != '?':\n",
    "                b1.append(int(i))\n",
    "        for i in a2:\n",
    "            if i != '?':\n",
    "                b2.append(int(i))\n",
    "        n2=len(b1)\n",
    "        n3=len(b2)\n",
    "        c=(sum(b1)-sum(b2))\n",
    "        if n2==n3:\n",
    "            return c!=0\n",
    "        else:\n",
    "            return c!=4.5*(n2-n3)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        n=len(num)\n",
    "        n1=n//2\n",
    "        a1=num[0:n1]\n",
    "        a2=num[n1:n]\n",
    "        b1=[]\n",
    "        b2=[]\n",
    "        for i in a1:\n",
    "            if i != '?':\n",
    "                b1.append(int(i))\n",
    "        for i in a2:\n",
    "            if i != '?':\n",
    "                b2.append(int(i))\n",
    "        n2=n1-len(b1)\n",
    "        n3=n1-len(b2)\n",
    "        c=abs(sum(b1)-sum(b2))\n",
    "        if n2==n3:\n",
    "            return c!=0\n",
    "        if n2<n3:\n",
    "            return sum(b1)-sum(b2)!=4.5*(n3-n2)\n",
    "        if n2>n3:\n",
    "            return sum(b2)-sum(b1)!=4.5*(n2-n3)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        n=len(num)\n",
    "        n1=n//2\n",
    "        a1=num[0:n1]\n",
    "        a2=num[n1:n]\n",
    "        b1=[]\n",
    "        b2=[]\n",
    "        for i in a1:\n",
    "            if i != '?':\n",
    "                b1.append(int(i))\n",
    "        for i in a2:\n",
    "            if i != '?':\n",
    "                b2.append(int(i))\n",
    "        n2=n1-len(b1)\n",
    "        n3=n1-len(b2)\n",
    "        c=sum(b1)-sum(b2)\n",
    "        if n2==n3:\n",
    "            return c!=0\n",
    "        if n2<n3:\n",
    "            return c!=4.5*(n3-n2)\n",
    "        if n2>n3:\n",
    "            return -c!=4.5*(n2-n3)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        n=len(num)\n",
    "        n1=n//2\n",
    "        a1=num[0:n1]\n",
    "        a2=num[n1:n]\n",
    "        b1=[]\n",
    "        b2=[]\n",
    "        for i in a1:\n",
    "            if i != '?':\n",
    "                b1.append(int(i))\n",
    "        for i in a2:\n",
    "            if i != '?':\n",
    "                b2.append(int(i))\n",
    "        n2=n1-len(b1)\n",
    "        n3=n1-len(b2)\n",
    "        c=sum(b1)-sum(b2)\n",
    "        if n2==n3:\n",
    "            return c!=0\n",
    "        if n2<n3:\n",
    "            return sum(b1)-sum(b2)!=4.5*(n3-n2)\n",
    "        if n2>n3:\n",
    "            return sum(b2)-sum(b1)!=4.5*(n2-n3)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        n=len(num)\n",
    "        n1=n//2\n",
    "        a1=num[0:n1]\n",
    "        a2=num[n1:n]\n",
    "        b1=[]\n",
    "        b2=[]\n",
    "        for i in a1:\n",
    "            if i != '?':\n",
    "                b1.append(int(i))\n",
    "        for i in a2:\n",
    "            if i != '?':\n",
    "                b2.append(int(i))\n",
    "        n2=n1-len(b1)\n",
    "        n3=n1-len(b2)\n",
    "        c=(sum(b1)-sum(b2))\n",
    "        if n2==n3:\n",
    "            return c!=0\n",
    "        else:\n",
    "            return c!=4.5*(n3-n2)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        n=len(num)\n",
    "        n1=n//2\n",
    "        a1=num[0:n1]\n",
    "        a2=num[n1:n]\n",
    "        b1=[]\n",
    "        b2=[]\n",
    "        for i in a1:\n",
    "            if i != '?':\n",
    "                b1.append(int(i))\n",
    "        for i in a2:\n",
    "            if i != '?':\n",
    "                b2.append(int(i))\n",
    "        n2=n1-len(b1)\n",
    "        n3=n1-len(b2)\n",
    "        c=abs(sum(b1)-sum(b2))\n",
    "        if n2==n3:\n",
    "            return c!=0\n",
    "        if n2<n3:\n",
    "            return sum(b1)-sum(b2)!=4.5*(n3-n2)\n",
    "        if n2>n3:\n",
    "            return sum(b2)-sum(b1)!=4.5*(n2-n3)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumGame(self, num: str) -> bool:\n",
    "        n=len(num)\n",
    "        n1=n//2\n",
    "        a1=num[0:n1]\n",
    "        a2=num[n1:n]\n",
    "        b1=[]\n",
    "        b2=[]\n",
    "        for i in a1:\n",
    "            if i != '?':\n",
    "                b1.append(int(i))\n",
    "        for i in a2:\n",
    "            if i != '?':\n",
    "                b2.append(int(i))\n",
    "        n2=n1-len(b1)\n",
    "        n3=n1-len(b2)\n",
    "        c=abs(sum(b1)-sum(b2))\n",
    "        if n2==n3:\n",
    "            return c!=0\n",
    "        if n2<n3:\n",
    "            return sum(b1)-sum(b2)!=4.5*(n3-n2)\n",
    "        if n2>n3:\n",
    "            return sum(b2)-sum(b1)!=4.5*(n2-n3)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
